//Priority queue based on binary heap

#ifndef HPQUEUE_H
#define HPQUEUE_H

//#include "RuntimeException.h"
//#include "PriorityQueue.h"
#include "BinaryHeap.h"

template <typename T>
class HPQueue {
protected:
	typedef Item<T> I;
	typedef PQComp<T> P;
private:
	BinaryHeap<I, P> Y;
	static const int DEF_SIZE = 8;
	//int cmps;
public:

	struct EmptyPriorityQueue : public RuntimeException {
		EmptyPriorityQueue() : RuntimeException("Queue is Empty") {}
	};
	
	HPQueue(int size = DEF_SIZE) : Y(size) {}
	bool empty() const { return Y.empty(); }
	int* insert_item(const unsigned int k, const T& e, int& num_cmps) {
		
		int* pos = new int[1];
		Y.insert(I(k,e,pos), num_cmps);
		//update_key(pos,k,num_cmps);
		return pos;
	}
	
	const T& min_elem() throw(EmptyPriorityQueue){
		if (Y.empty()) throw EmptyPriorityQueue();
		return Y.find_min().get_elem();
	}
	
	const int min_key() throw(EmptyPriorityQueue) {
		if (Y.empty()) throw EmptyPriorityQueue();
		return Y.find_min().get_key();
	}
	
	void remove_min(int& num_cmps) throw(EmptyPriorityQueue) {
		if (Y.empty()) throw EmptyPriorityQueue();
		Y.delete_min(num_cmps);
	}
	
	void update_key(int* pos, unsigned int k, int& num_cmps) {
		
		if (Y.array[*pos].get_key() < k)
		{
			Y.array[*pos].set_key(k);
			Y.walk_down(*pos, num_cmps);
		}
		else
		{
			Y.array[*pos].set_key(k);
			I i(k,Y.array[*pos].get_elem(),Y.array[*pos].pos);
			Y.walk_up(i, *pos, num_cmps);
		}
    }
    
	int size(){ return Y.size(); }
    void print()
	{
		if (Y.empty()){
			std::cout << "Queue is empty. Moving on.\n";
		}
		for (int i = 0; i < Y.size(); i++)
		{
			std::cout << "Element: " << Y.array[i].get_elem()
				<< "; Key: " << Y.array[i].get_key() << '\n';
		}
	}
    //void get_cmps(){ return cmps; }
};

#endif
